package day1114;

/**
 * @Author 比特就业课
 * @Date 2022-11-14
 */
public class BinarySearchTree {
    // 定义节点类
    private static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
    // 定义一个根节点的引用
    public TreeNode root;

    /**
     * 查找指定的值是否存在
     * @param value
     * @return
     */
    public boolean search(int value) {

        return false;
    }

    /**
     * 插入一个元素
     * @param value 要插入的值
     * @return
     */
    public boolean insert(int value) {
        TreeNode node=new TreeNode(value);
        if(root==null){
            root=node;
            return true;
        }
        TreeNode current=root;
        TreeNode prev=null;
        while(current!=null){
            prev=current;
            if(current.value>value){
                current=current.right;
            }else if(current.value<value){
                current=current.left;
            }else {
                return false;
            }
        }
//        此时prev为叶子节点，判断node节点位于其左侧还是右侧
        if(value< prev.value){
            prev.left=node;
        }else {
            prev.right=node;
        }
        return  true;

    }

    /**
     * 删除指定的元素
     * @param value 要删除的元素
     * @return
     */
    public boolean remove(int value) {

        return false;
    }

    /**
     * 中序遍历
     * @param node
     * @return
     */
    public String inorder(TreeNode node) {
        StringBuilder sb = new StringBuilder();
        if (node == null) {
            return sb.toString();
        }
        // 先处理左
        String left = inorder(node.left);
        sb.append(left);
        // 处理根节点
        sb.append(node.value + " ");
        // 处理右
        String right = inorder(node.right);
        sb.append(right);
        return sb.toString();
    }
}
